package com.kongge.algorithm.demo;

/**
 * 数组中有一个数字出现的次数超过数组的一半，请找出这个数字
 * @author kongge
 *
 */
public class MoreThenHalfNum implements IAlgorithm{

	public void execute() {
		int[] numArr = {1, 2, 3, 2, 2, 2, 5, 4, 2};
		Integer resultInteger = getMoreThenHalfNum(numArr);
		if (resultInteger == null) {
			System.out.println("Can't find!");
		} else {
			System.out.println("The result is " + resultInteger);
		}
	}
	
	private Integer getMoreThenHalfNum(int[] numArr) {
		if (numArr == null || numArr.length <= 0) {
			return null;
		}
		Integer numInteger = null;
		int curNum = numArr[0];
		int curNumShowTime = 1;
		for (int i = 1; i < numArr.length; i++) {
			int numChild = numArr[i];
			if (curNum == numChild) {
				curNumShowTime++;
			} else {
				curNumShowTime--;
				if (curNumShowTime <= 0) {
					curNum = numChild;
					curNumShowTime = 1;
				}
			}
		}
		if (curNumShowTime > 0 && check(numArr, curNum)) {
			return new Integer(curNum);
		}
		return numInteger;
	}
	
	private boolean check(int[] numArr, int number) {
		if (numArr == null || numArr.length <= 0) {
			return false;
		}
		int times = 0;
		for (int i = 0; i < numArr.length; i++) {
			if (numArr[i] == number) {
				times++;
			}
		}
		if (times > numArr.length / 2) {
			return true;
		}
		return false;
	}
}
